In many communications systems, there is a need to compute correlations between a received signal and a known sequence. This is particularly true for wireless communications systems such as cellular telephone systems.
Correlation, as used herein, is a process by which a sample sequence is compared or matched against a known sequence to determine where, or if, the known sequence is present in the sample sequence. Examples of when correlation is used include synchronization and joint demodulation in many wireless systems such as GSM, D-AMPS, and TETRA, as well as code acquisition in CDMA systems such as IS-95. Proper correlation is very important for proper functioning of these systems.
Typically, the sample sequence is a received signal and the correlation process attempts to either determine the start of a communications frame (synchronization) or separate commingled signals (joint demodulation). The traditional correlation process is computationally intensive; the known sequence is compared against the sample sequence in an increment-by-increment fashion. For each incremental comparison, a correlation factor, or score, is obtained. The highest correlation factor identifies the best fit of the known sequence to the sample sequence, which should correspond to the location in the sample sequence where the known sequence appears.
Consider a simple synchronization example for a communications signal divided into groups known as communications frames. For a receiver to properly interpret a received signal, the receiver must be able to determine where one frame begins and another ends. In order to facilitate this, each frame contains a known synchronization sequence in addition to the communications data. For simplicity, assume that the synchronization (sync) sequence is at the beginning of each frame. At the transmitter, a frame is constructed using a block of data and the known sync sequence s=(s.sub.0, s.sub.1, . . . s.sub.L-1) having a length L to identify the boundaries of the frame. The transmitter combines one or more frames and transmits the frames as a communications signal to a receiver. The receiver assembles the received signal into a received sequence r=(r.sub.0, r.sub.1, . . . r.sub.F-1). The receiver then determines the boundaries of the frame by correlating the received sequence r with the known sync sequence s. The correlation of the received sequence to the sync sequence involves calculating a series of correlation factors C.sub.j, and then selecting the correlation factor having the highest value. The correlation factors are calculated according to the formula ##EQU1## for a range of values, say 0.ltoreq.j&lt;N-1, where N=F-L+1 and F is frame length in number of elements. Note that it is always assumed that L.ltoreq.F, i. e., the known sync sequence length is no larger than the frame length. In FIG. 1, L is seven, F is fifteen, meaning N is nine. In simple terms, N represents the number of correlation factors that must be computed for each correlation.
The formula above is essentially the mathematical equivalent of laying the known sync sequence over the received signal to determine where the best fit is. When the fit is best, the correlation factor should be the highest, indicating the location of a frame boundary. Once the frame boundary is known, the data content of the frame can be properly interpreted.
Assuming the sync sequence is a bipolar (.+-.1) sequence, and the received sequence is comprised of real numbers, then the calculation of each correlation factor C.sub.j requires L-1 additions, for a total of N.times.(L-1) additions for all correlation factors C. If the received sequence is comprised of complex numbers, and assuming that adding two complex numbers requires two additions, the calculation of each correlation factor C.sub.j requires 2(L-1) additions, for a total of 2N.times.(L-1) additions for all correlation factors C. When the number of correlation factors N and the sync sequence length L are small, this prior art method for calculating correlation factors C does not impose a large computational burden. However, when number of correlation factors N and/or the sync sequence length L are large, then this traditional straightforward method of calculating correlation factors C is computationally burdensome. Further, where one received sequence is to be compared against a plurality of known sequences, such as in CDMA systems, the traditional straightforward method of calculating correlation factors is particularly inefficient.
Because many of the more advanced wireless communications systems rely on correlation schemes having large numbers of correlation factors N and large sync sequence lengths L, and because many compare a received sequence against a plurality of known sequences, there is a need for a more efficient method of computing sequence correlations.